/**
 * 174、地下城游戏
 */
public class Exercise10 {
    // 为什么不用 以i,j为终点的思路呢？
    // 因为这样需要i,j位置的左面值和上面值，并且需要之后i,j位置的左面值和下面值才能知道这个位置的最小健康点数
    public int calculateMinimumHP(int[][] dungeon) {
        // dp[i][j]: 以i,j为起点，到达终点位置,所需要的最低健康点数
        int m = dungeon.length,n = dungeon[0].length;
        int[][] dp = new int[m + 1][n + 1];
        for(int j = 0;j <= n;j++) {
            dp[m][j] = Integer.MAX_VALUE;
        }
        for(int i = 0;i <= m;i++) {
            dp[i][n] = Integer.MAX_VALUE;
        }
        dp[m][n - 1] = dp[m - 1][n] = 1;
        for(int i = m - 1;i >= 0;i--) {
            for(int j = n - 1;j >= 0;j--) {
                dp[i][j] = Math.min(dp[i][j + 1],dp[i + 1][j]) - dungeon[i][j];
                dp[i][j] = Math.max(1,dp[i][j]); // 这里是防止 dungeon[i][j] 是一个很大的正整数
            }
        }
        return dp[0][0];
    }
}
